package com.mlh.binarysearch;

import com.mlh.backtracking.电话号码的字母组合;

/**
 * @author 缪林辉
 * @date 2024/8/29 20:14
 * @DESCRIPTION
 */
//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
// 请必须使用时间复杂度为 O(log n) 的算法。
public class 搜索插入位置 {
    public int method1(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while (left<right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        //当left=right退出循环 判断
        if(nums[left]<target){
            return left+1;
        }else {//如果nums[left]==target 或者 nums[left]>target  target都应该在left位置
            return left;
        }
    }
    public int practice(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                return mid;
            }
        }
        if(nums[left]<target){
            return left+1;
        }else{
            return left;
        }
    }
}
